package com.leetCode.problem;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-05 16:23:00
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-05     张李鑫                     1.0         1.0 Version
 */

public class Problem34 {
    /**
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * <p>
     * 如果数组中不存在目标值 target，返回[-1, -1]。
     * <p>
     * 进阶：
     * <p>
     * 你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static int[] searchRange(int[] nums, int target) {
        if (null == nums || nums.length == 0) {
            return new int[]{-1, -1};
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = left + (right >> 1);
        while (left <= right) {
            mid = left + (right - left >> 1);
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                break;
            }
        }
        if (target != nums[mid]) {
            return new int[]{-1, -1};
        }
        left = mid - 1;
        right = mid + 1;
        while (left >= 0) {
            if (nums[left] == target) {
                left--;
            } else {
                break;
            }
        }
        while (right < nums.length) {
            if (nums[right] == target) {
                right++;
            } else {
                break;
            }
        }
        return new int[]{++left, --right};
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 7, 8, 8, 10,16,14};
        int[] ints = searchRange(arr, 8);
        System.out.println(ints[0]);
        System.out.println(ints[1]);
    }
}
